\section{Proofs for Section~\ref{sec:prelim}}
\label{app:prelim}
\begin{LabeledProof}{Lemma~\ref{lem:moreneighbor-10p}}
  If $\nei{t}{3}{u}$ is not an empty set, consider node $v\in
  \nei{t}{3}{u}$. Since $\dg{t}{v} \ge \md{t}$, we have
  $\abs{\cup_{i=2}^4 \nei{t}{i}{u}} \ge
  \md{t}$. $\abs{\nei{t}{1}{u}}\ge \md{t}$ because $\dg{t}{u}\ge
  \md{t}$. We also know $\nei{t}{1}{u}$ and $\cup_{i=2}^4
  \nei{t}{i}{u}$ are disjoint. Thus, $\abs{\cup_{i=1}^4 \nei{t}{i}{u}}
  \ge 2\md{t}$.  If $\nei{t}{3}{u}$ is an empty set, then
  $\nei{t}{1}{u}\cup \nei{t}{2}{u}=n-1$ because $\gf{t}$ is
  connected. Thus $\abs{\cup_{i=1}^4 \nei{t}{i}{u}} = n-1$. Combine
  the above 2 cases, we complete the proof of this lemma.
\end{LabeledProof}

\begin{LabeledProof}{Lemma~\ref{lem:moreneighbor-10p}}
  Since $X$ only increases with $k$, with out loss of generality
  assume that $k = m$. Now we can view this as {\em coupon collector
    problem} \cite{upfal} where $X_{m+1-i}$ is the number of steps to
  collect the $i$th coupon. Consider the probability of not obtaining
  the $i$th coupon after $(c+1)m\ln m$ steps. This probability is
\[\rb{1-\frac{1}{m}}^{(c+1)m\ln m} < e^{-(c+1)\ln m} =
\frac{1}{m^{c+1}}\] By union bound, the probability that some coupon
has not been collected after $(c+1)m\ln m$ steps is less than
$1/m^c$. And this completes the proof of this lemma.
\end{LabeledProof}

